#define _CRT_SECURE_NO_WARNINGS 1

using namespace std;
#include <vector>
#include <string>

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int left = 0, right = n - 1;
        int cur = 0;
        while (cur <= right)
        {
            if (nums[cur] == 0)
            {
                swap(nums[cur], nums[left]);
                left++;
                cur++;
            }
            else if (nums[cur] == 1)
                cur++;
            else
            {
                swap(nums[cur], nums[right]);
                right--;
            }
        }
    }
};

class Solution {
public:
    string breakPalindrome(string palindrome) {
        int n = palindrome.size();
        if (n == 1)
            return "";
        for (int i = 0; i < n / 2; i++)
        {
            if (palindrome[i] != 'a')
            {
                palindrome[i] = 'a';
                return palindrome;
            }
        }
        palindrome[n - 1] = 'b';
        return palindrome;
    }
};